package net.tp.algo.text.sa;

import net.tp.util.Wrappers;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Function;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * <p>Suffix Array.</p>
 *
 *
 * <p class="svg">
 * {@code
 * <svg version="1.1" width="340" height="270"><g transform="translate(0,-30)" id="layer2"><path d="m 290.75861,284.17251 0,-237.31825" id="path4212" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 319.43917,284.17251 0,-237.31825" id="path4216" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 304.30221,284.17251 0,-237.31825" id="path4214" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 275.62165,284.17251 0,-237.31825" id="path4210" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 261.28137,284.17251 0,-237.31825" id="path4208" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 15.903351,284.17251 0,-237.31825" id="path4174" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 31.040304,284.17251 0,-237.31825" id="path4176" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 46.97394,284.17251 0,-237.31825" id="path4178" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 61.314212,284.17251 0,-237.31825" id="path4180" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 75.361,284.17251 0,-237.31825" id="path4182" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 89.994756,284.17251 0,-237.31825" id="path4184" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 104.135,284.17251 0,-237.31825" id="path4186" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 118.6753,284.17251 0,-237.31825" id="path4188" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 133.01557,284.17251 0,-237.31825" id="path4190" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 146.55916,284.17251 0,-237.31825" id="path4192" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 161.69612,284.17251 0,-237.31825" id="path4194" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 176.83307,284.17251 0,-237.31825" id="path4196" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 190.37666,284.17251 0,-237.31825" id="path4198" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 204.71693,284.17251 0,-237.31825" id="path4200" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 219.05721,284.17251 0,-237.31825" id="path4202" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 233.39749,284.17251 0,-237.31825" id="path4204" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /><path d="m 246.94109,284.17251 0,-237.31825" id="path4206" style="fill:none;stroke:#000000;stroke-width:0.2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" /></g><g transform="translate(0,-782.36218)" id="layer1"><path d="M 16.094353,824.84444 31.275272,967.4531" id="path4027" style="fill:none;stroke:#000000;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><path d="m 31.275272,967.4531 16.00552,-13.0182 13.877204,-94.67798 13.9058,13.60994 14.79342,67.75388" id="path4025" style="fill:none;stroke:#ff0000;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><path d="m 89.857216,941.12074 13.905824,-12.42648 15.0893,-35.80008 14.49754,13.01822 13.60996,61.5407" id="path4017" style="fill:none;stroke:#0000ff;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><path d="m 146.95984,967.4531 15.38514,-13.0182 14.79342,-94.67798 13.60994,13.60994 14.49755,67.75388" id="path4009" style="fill:none;stroke:#ff0000;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><path d="m 205.24589,941.12074 14.20168,-12.42648 14.2017,-35.80008 14.20168,13.01822 13.90582,61.5407" id="path4001" style="fill:none;stroke:#0000ff;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><path d="m 261.75677,967.4531 14.20168,-1.7988 15.38516,-23.24022 13.90582,25.03902 15.08928,13.61914" id="path3993" style="fill:none;stroke:#008000;stroke-width:2px;stroke-linecap:round;stroke-linejoin:round;stroke-opacity:1" /><text x="13.399281" y="818.15375" id="text3897" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="13.399281" y="818.15375" id="tspan3899">L</tspan></text><text x="57.295521" y="854.87469" id="text3901" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="57.295521" y="854.87469" id="tspan3903">L</tspan></text><text x="72.490387" y="867.95917" id="text3905" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="72.490387" y="867.95917" id="tspan3907">L</tspan></text><text x="172.52316" y="854.87469" id="text3909" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="172.52316" y="854.87469" id="tspan3911">L</tspan></text><text x="187.71805" y="867.95917" id="text3913" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="187.71805" y="867.95917" id="tspan3915">L</tspan></text><text x="115.12038" y="887.37482" id="text3917" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="115.12038" y="887.37482" id="tspan3919">L</tspan></text><text x="130.31528" y="900.45929" id="text3921" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="130.31528" y="900.45929" id="tspan3923">L</tspan></text><text x="229.50386" y="886.10858" id="text3925" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="229.50386" y="886.10858" id="tspan3927">L</tspan></text><text x="244.69872" y="899.19305" id="text3929" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="244.69872" y="899.19305" id="tspan3931">L</tspan></text><text x="21.217518" y="982.34259" id="text3933" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="21.217518" y="982.34259" id="tspan3935">S*</tspan></text><text x="45.678608" y="968.21271" id="text3937" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="45.678608" y="968.21271" id="tspan3939">S</tspan></text><text x="138.13348" y="982.76495" id="text3941" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="138.13348" y="982.76495" id="tspan3943">S*</tspan></text><text x="162.59454" y="968.6347" id="text3945" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="162.59454" y="968.6347" id="tspan3947">S</tspan></text><text x="195.53625" y="956.59576" id="text3949" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="195.53625" y="956.59576" id="tspan3951">S*</tspan></text><text x="219.99731" y="942.46588" id="text3953" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="219.99731" y="942.46588" id="tspan3955">S</tspan></text><text x="79.886536" y="957.01788" id="text3957" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="79.886536" y="957.01788" id="tspan3959">S*</tspan></text><text x="104.34763" y="942.888" id="text3961" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="104.34763" y="942.888" id="tspan3963">S</tspan></text><text x="250.82861" y="980.47247" id="text3965" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="250.82861" y="980.47247" id="tspan3967">S*</tspan></text><text x="275.28964" y="978.34296" id="text3969" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="275.28964" y="978.34296" id="tspan3971">S</tspan></text><text x="311.608" y="995.88812" id="text3973" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="311.608" y="995.88812" id="tspan3975">S*</tspan></text><text x="287.75076" y="937.84259" id="text3977" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="287.75076" y="937.84259" id="tspan3979">L</tspan></text><text x="302.94565" y="960.92719" id="text3981" xml:space="preserve" style="font-size:16px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="302.94565" y="960.92719" id="tspan3983">L</tspan></text><text x="10.476917" y="1024.5165" id="text4086" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="10.476917" y="1024.5165" id="tspan4088">y</tspan></text><text x="24.650259" y="1024.5165" id="text4090" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="24.650259" y="1024.5165" id="tspan4092">a</tspan></text><text x="40.764877" y="1024.5165" id="text4094" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="40.764877" y="1024.5165" id="tspan4096">b</tspan></text><text x="54.06041" y="1024.5165" id="text4098" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="54.06041" y="1024.5165" id="tspan4100">t</tspan></text><text x="68.349251" y="1024.5165" id="text4102" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="68.349251" y="1024.5165" id="tspan4104">s</tspan></text><text x="81.810844" y="1024.5165" id="text4106" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="81.810844" y="1024.5165" id="tspan4108">c</tspan></text><text x="96.326218" y="1024.5165" id="text4110" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="96.326218" y="1024.5165" id="tspan4112">d</tspan></text><text x="110.43703" y="1024.5165" id="text4114" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="110.43703" y="1024.5165" id="tspan4116">q</tspan></text><text x="125.944" y="1024.5165" id="text4118" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="125.944" y="1024.5165" id="tspan4120">p</tspan></text><text x="139.37245" y="1024.5165" id="text4122" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="139.37245" y="1024.5165" id="tspan4124">a</tspan></text><text x="155.48706" y="1024.5165" id="text4126" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="155.48706" y="1024.5165" id="tspan4128">b</tspan></text><text x="168.78259" y="1024.5165" id="text4130" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="168.78259" y="1024.5165" id="tspan4132">t</tspan></text><text x="183.07144" y="1024.5165" id="text4134" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="183.07144" y="1024.5165" id="tspan4136">s</tspan></text><text x="196.53304" y="1024.5165" id="text4138" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="196.53304" y="1024.5165" id="tspan4140">c</tspan></text><text x="211.04842" y="1024.5165" id="text4142" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="211.04842" y="1024.5165" id="tspan4144">d</tspan></text><text x="225.15924" y="1024.5165" id="text4146" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="225.15924" y="1024.5165" id="tspan4148">q</tspan></text><text x="240.6662" y="1024.5165" id="text4150" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="240.6662" y="1024.5165" id="tspan4152">p</tspan></text><text x="254.27985" y="1024.5165" id="text4154" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="254.27985" y="1024.5165" id="tspan4156">a</tspan></text><text x="268.77582" y="1024.5165" id="text4158" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="268.77582" y="1024.5165" id="tspan4160">a</tspan></text><text x="298.35181" y="1024.5165" id="text4162" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="298.35181" y="1024.5165" id="tspan4164">a</tspan></text><text x="284.05487" y="1024.5165" id="text4166" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="284.05487" y="1024.5165" id="tspan4168">c</tspan></text><text x="311.82745" y="1024.5165" id="text4170" xml:space="preserve" style="font-size:24px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="311.82745" y="1024.5165" id="tspan4172">$</tspan></text></g></svg>
 * }
 * </p>
 *
 *
 * <pre>
 *          i:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21
 *          S:  y  a  b  t  s  c  d  q  p  a  b  t  s  c  d  q  p  a  a  c  a  $
 *       Type:  L  S  S  L  L  S  S  L  L  S  S  L  L  S  S  L  L  S  S  L  L  S
 *        LMS:     *           *           *           *           *           *
 *     Bucket:  $  a  a  a  a  a  b  b  c  c  c  d  d  p  p  q  q  s  s  t  t  y
 *         P1:  1  5  9 13 17 21
 *    P1 → SA: 21        1  9 17           5 13
 *     L → SA: 21 20     1  9 17       19  5 13        8 16  7 15  4 12  3 11  0
 *     S → SA: 21 20 17  1  9 18  2 10 19  5 13  6 14  8 16  7 15  4 12  3 11  0
 *      Names:  2  3  2  3  1  0
 *          i:  0  1  2  3  4  5
 *          S:  2  3  2  3  1  0
 *       Type:  S  L  S  L  L  S
 *        LMS:        *        *
 *     Bucket:  0  1  2  2  3  3
 *         P1:  2  5
 *    P1 → SA:  5        2
 *     L → SA:  5  4     2  3  1
 *     S → SA:  5  4  2  0  3  1
 *      Names:  1  0
 *  sorted P1:  5  2
 *    P1 → SA:  5        2
 *     L → SA:  5  4     2  3  1
 *     S → SA:  5  4  2  0  3  1
 *  sorted P1: 21 17  9  1 13  5
 *    P1 → SA: 21       17  9  1          13  5
 *     L → SA: 21 20    17  9  1       19 13  5       16  8 15  7 12  4 11  3  0
 *     S → SA: 21 20 17  9  1 18 10  2 19 13  5 14  6 16  8 15  7 12  4 11  3  0
 *
 * </pre>
 *
 *
 * @author Trung Phan
 */
public class SAIS {

    private static final Logger logger = Logger.getLogger(SAIS.class.getName());
    private static StringBuilder logBuilder;

    public static int[] buildSA(IntString text, int k) {

        int n = text.length();

        boolean[] isS = classifySLType(text); // can use bit array to save space

        if (logger.isLoggable(Level.FINE)) {
            logStep(Wrappers.sequence(0, n), "i");
            logStep(text, "S");
            Function<Boolean, String> f = (b) -> b ? "S" : "L"; // workaround for bug id 9004373
            logStep(Wrappers.makeIterable(Wrappers.makeIterable(isS), f ), "Type"  );
            Function<Integer, String> f2 = (i) -> isLMS(isS, i) ? "*" : "";
            logStep(Wrappers.makeIterable(Wrappers.sequence(0, n), f2), "LMS");
            logBuckets(text, k, "Bucket");
        }


        int n1 = getLMSCount(isS);

        int[] P1 = new int[n1]; // P1 is not necessary to create, it's easier to follow the algorithm with P1.
        int[] P1i = new int[n];
        Arrays.fill(P1i, -1);

        for (int i = 1, j = 0; i < isS.length; i++) {
            if (isLMS(isS, i)) {
                P1[j] = i;
                P1i[i] = j;
                j++;
            }
        }

        logStep(P1, "P1");

        int[] SA = new int[n];
        Arrays.fill(SA, -1);

        int[] buckets = buckets(text, k, false);

        for (int i = P1.length - 1; i >= 0; i--) {
            SA[--buckets[ text.charAt(P1[i])]] = P1[i];
        }

        logStep(SA, "P1 → SA");

        buckets = buckets(text, k, true);
        for (int i = 0; i < SA.length; i++) {
            if (SA[i] > 0 && !isS[SA[i]-1]) {
                SA[buckets[text.charAt(SA[i]-1)]++] = SA[i]-1;
            }
        }

        logStep(SA, "L → SA");

        buckets = buckets(text, k, false);
        for (int i = SA.length - 1; i >=0; i--) {
            if (SA[i] > 0 && isS[SA[i]-1]) {
                SA[--buckets[text.charAt(SA[i]-1)]] = SA[i]-1;
            }
        }

        logStep(SA, "S → SA");

        Arrays.fill(P1, 0);
        for (int i = 0, j = 0; i < SA.length; i++) {
            if (isLMS(isS, SA[i])) P1[j++] = SA[i];
        }

        int name = 0;
        int[] s1 = new int[n1];
        s1[P1i[P1[0]]] = name;
        for (int i = 1; i < n1; i++) {
            int a = P1[i], b = P1[i-1];
            boolean diff = false;
            for (int d = 0;; d++) {
                if (text.charAt(a+d) != text.charAt(b+d) || isS[a+d] != isS[b+d] || isLMS(isS, a+d) != isLMS(isS, b+d)) {
                    diff = true; break;
                }
                if (d > 0 && isLMS(isS, a+d)) break;
            }
            if (diff) s1[P1i[P1[i]]] = ++name;
            else s1[P1i[P1[i]]] = name;
        }

        logStep(s1, "Names");

        if (name < n1-1) {

            int[] SA1 = buildSA(IntString.valueOf(s1), name);
            int[] rank1 = new int[SA1.length];
            for (int i = 0; i < SA1.length; i++) {
                rank1[SA1[i]] = i;
            }

            for (int i = 1, j = 0; i < isS.length; i++) {
                if (isLMS(isS, i)) P1[rank1[j++]] = i;
            }
        }

        logStep(P1, "sorted P1");

        Arrays.fill(SA, -1);

        buckets = buckets(text, k, false);
        for (int i = P1.length - 1; i >= 0; i--) {
            SA[--buckets[ text.charAt(P1[i])]] = P1[i];
        }

        logStep(SA, "P1 → SA");

        buckets = buckets(text, k, true);
        for (int i = 0; i < SA.length; i++) {
            if (SA[i] > 0 && !isS[SA[i]-1]) {
                SA[buckets[text.charAt(SA[i]-1)]++] = SA[i]-1;
            }
        }

        logStep(SA, "L → SA");

        buckets = buckets(text, k, false);
        for (int i = SA.length - 1; i >= 0; i--) {
            if (SA[i] > 0 && isS[SA[i]-1]) {
                SA[--buckets[text.charAt(SA[i]-1)]] = SA[i]-1;
            }
        }

        logStep(SA, "S → SA");

        return SA;
    }

    /**
     *
     * addccc$ =>
     * $acd
     * 1132
     * 0125 (begin)
     * 1257 (end)
     *
     * @param text
     * @param k
     * @return
     */
    private static int[] buckets(IntString text, int k, boolean begin) {
        int[] buckets = new int[k + 1];
        for (int i = 0; i < text.length(); i++) {
            buckets[text.charAt(i)]++;
        }
        if (begin) {
            for (int i = 0, sum = 0; i < buckets.length; i++) {
                int tmp = buckets[i]; buckets[i] = sum; sum += tmp;
            }
        }
        else {
            for (int i = 1; i < buckets.length; i++) {
                buckets[i] += buckets[i-1];
            }
        }

        return buckets;
    }

    private static boolean isLMS(boolean[] isS, int i) {
        return i > 0 && isS[i] && !isS[i-1];
    }

    private static int getLMSCount(boolean[] isS) {
        int n1 = 0;
        for (int i = 1; i < isS.length; i++) {
            if (isS[i] && !isS[i-1]) n1++;
        }
        return n1;
    }

    /**
     * 1 means L (larger)
     * 0 means S (smaller)
     * @param text
     * @return
     */
    private static boolean[] classifySLType(IntString text) {
        int n = text.length();
        boolean[] isS = new boolean[n];
        isS[n-1] = true;
        for (int i = n - 2; i >= 0; i--) {
            if (text.charAt(i) > text.charAt(i+1)) {
                isS[i] = false;
            }
            else if (text.charAt(i) < text.charAt(i+1)) {
                isS[i] = true;
            }
            else isS[i] = isS[i+1];
        }
        return isS;
    }


    public static void main(String ... args) {
        String text = "yabtscdqpabtscdqpaaca$";

        logBegin();
        int[]sa = buildSA(IntString.valueOf(text), (int)'y');
        logEnd();

        System.out.println(Arrays.toString(NaiveSA.buildSA(text)));
    }

    private static void logBegin() {
        if (logger.isLoggable(Level.FINE)) {
            logBuilder = new StringBuilder('\n');
        }
    }

    private static void logStep(int[] a, String stepDescription) {
        if (logger.isLoggable(Level.FINE) && a != null) {
            logBuilder.append(String.format("\n%10s:", stepDescription));
            for (int i = 0; i < a.length; i++) {
                if (a[i] == -1) {
                    logBuilder.append("   ");
                }
                else {
                    logBuilder.append(String.format("%3d", a[i]));
                }
            }
        }
    }

    private static void logStep(Iterable<?> a, String stepDescription) {
        if (logger.isLoggable(Level.FINE) && a != null) {
            logBuilder.append(String.format("\n%10s:", stepDescription));
            for (Object o : a) {
                logBuilder.append(String.format("%3s", o.toString()));
            }
        }
    }

    private static void logStep(IntString s, String stepDescription) {
        if (logger.isLoggable(Level.FINE) && s != null) {
            boolean isChar = s instanceof IntString.StringBackedIntString || s instanceof IntString.SubstringBackedIntString;
            logBuilder.append(String.format("\n%10s:", stepDescription));
            for (int i = 0; i < s.length(); i++) {
                int c = s.charAt(i);
                if (isChar) {
                    logBuilder.append(String.format("%3c", (char)c));
                }
                else {
                    logBuilder.append(String.format("%3d", c));
                }
            }
        }
    }

    private static void logBuckets(IntString s, int k, String stepDescription) {
        if (logger.isLoggable(Level.FINE) && s != null) {
            boolean isChar = s instanceof IntString.StringBackedIntString || s instanceof IntString.SubstringBackedIntString;
            logBuilder.append(String.format("\n%10s:", stepDescription));

            int[] cnt = new int[k + 1];
            for (int i = 0; i < s.length(); i++) {
                cnt[s.charAt(i)]++;
            }

            for (int i = 0, j = 0; i < cnt.length; i++) {
                while (cnt[i] > 0) {
                    if (isChar) {
                        logBuilder.append(String.format("%3c", (char)i));
                    }
                    else {
                        logBuilder.append(String.format("%3d", i));
                    }
                    cnt[i]--;
                }
            }
        }
    }

    private static void logEnd() {
        if (logger.isLoggable(Level.FINE)) {
            logger.fine(logBuilder.toString());
            logBuilder = null;
        }
    }

}
